
package main

import (
	"container/list"
	"fmt"
)

func solution(n int, k int, data []int) int {
	// 如果k >= n，可以在第一天购买所有需要的食物
	if k >= n {
		min := data[0]
		for _, num := range data {
			if num < min {
				min = num
			}
		}
		return min * n
	}

	mins := list.New()
	result := 0

	for j := 0; j < n; j++ {
		// 维护单调队列，确保队列中的元素是递增的
		for mins.Len() > 0 && mins.Back().Value.([]int)[1] > data[j] {
			mins.Remove(mins.Back())
		}
		// 将当前元素加入队列
		mins.PushBack([]int{j, data[j]})
		// 移除窗口外的元素
		for mins.Len() > 0 && mins.Front().Value.([]int)[0] <= j-k {
			mins.Remove(mins.Front())
		}
		// 累加当前窗口的最小价格
		result += mins.Front().Value.([]int)[1]
	}
	return result
}

func main() {
	// 测试样例
	fmt.Println(solution(5, 2, []int{1, 2, 3, 3, 2}) == 9)
	fmt.Println(solution(6, 3, []int{4, 1, 5, 2, 1, 3}) == 9)
	fmt.Println(solution(4, 1, []int{3, 2, 4, 1}) == 10)
	// 测试k >= n的情况
	fmt.Println(solution(4, 4, []int{3, 2, 4, 1}) == 4)
	fmt.Println(solution(4, 5, []int{3, 2, 4, 1}) == 4)
}
